Add binary

Time: O(N); Space: O(1); easy

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = “11”, b = “1”

Output: “100”

Example 2:

Input: a = “1010”, b = “1011”

Output: “10101”

Constraints:

  • Each string consists only of ‘0’ or ‘1’ characters.

  • 1 <= a.length, b.length <= 10^4

  • Each string is either “0” or doesn’t contain any leading zero.

[1]:

class Solution1(object):
    def addBinary(self, a, b):
        """
        :type a: string
        :type b: string
        :rtype: string
        """
        result, carry, val = "", 0, 0

        for i in range(max(len(a), len(b))):
            val = carry
            if i < len(a):
                val += int(a[-(i + 1)])
            if i < len(b):
                val += int(b[-(i + 1)])
            carry, val = val // 2, val % 2
            result += str(val)
        if carry:
            result += str(carry)

        return result[::-1]

[2]:

s = Solution1()

a = "11"
b = "1"
assert s.addBinary(a, b) == "100"

a = "1010"
b = "1011"
assert s.addBinary(a, b) == "10101"